package com.gorkr.hot100.medium;

import org.junit.jupiter.api.Test;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2023-01-10
 */
public class M240SearchA2dMatrixII {
    private boolean res = false;

    public boolean searchMatrix(int[][] matrix, int target) {

        backTrace(matrix, target, 0, 0);
        return res;
    }

    private void backTrace(int[][] matrix, int target, int i, int j){
        if(matrix[i][j] == target){
            res = true;
            return;
        }

        if((j+1)<matrix[0].length && matrix[i][j] < target){
            backTrace(matrix, target, i, j+1);
        }
        if((i+1)<matrix.length && matrix[i][j] < target) {
            backTrace(matrix, target, i + 1, j);
        }
    }

    @Test
    public void test(){
//        int[][] matrix = new int[][] {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24},
//                {18, 21, 23, 26, 30}};
        int[][] matrix = new int[][] {{1}};
        System.out.println(searchMatrix(matrix, 5));
    }

}
